home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 7057 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.7 KB  |  58 lines
  1. Path: soap.news.pipex.net!pipex!usenet
  2. From: m.hendry@dial.pipex.com (Mathew Hendry)
  3. Newsgroups: comp.sys.amiga.programmer
  4. Subject: Re: 680X0 -> PPC translator?
  5. Date: Mon, 8 Apr 96 15:50:52
  6. Organization: Private node.
  7. Distribution: world
  8. Message-ID: <19960408.40F118.E8F9@an052.du.pipex.com>
  9. References: <31499F8E.26A9@netvision.net.il> <volker.0fw1@vb.franken.de>
  10. NNTP-Posting-Host: an052.du.pipex.com
  11. X-Newsreader: TIN [AMIGA 1.3 950726BETA PL0]
  12.  
  13. Jack (avilev@netvision.net.il) wrote:
  14. : Mans Engman wrote:
  15. : > Once you think a bit, it's easy to show (prove!) that static code<->data
  16. : > distinction can't be determined by an algorithm. It is what theorists call
  17. : > an "undecidable" problem. Granted, for a "real" computer with a finite amount
  18. : > of memory/indata it can be "solved" by brute-force search, but this is
  19. : > not a practical approach.
  20. : 
  21. : many problems aren't solvable with today's technology, but it doesn't mean
  22. : they're not solvable with other yet-to-devised methods, now do they??
  23.  
  24. Some may be solved by new algorithms, but no finite number of algorithms can
  25. solve all problems. You surely can't be suggesting that your static translator
  26. will contain an infinite number of algorithms - or one infinitely large one.
  27.  
  28. In any case, we ARE talking about today's technology...
  29.  
  30. : > 
  31. : > Okay, let's go on:
  32. : > 
  33. : > 1) Hilberts 10th problem is a well known, proven undecidable problem. The
  34. : > problem is determining whether an integer polynomial equation has a
  35. : > (integer) solution.
  36. : 
  37. : oh please, stick to the subject at hand and stop making irrelevant analogies.
  38.  
  39. The analogy is not irrelevant. G÷del's theorem extends to ANY finite set of
  40. algorithms applied to generalised problems. It says that no set of algorithms
  41. (conceptually, these algorithms may be merged into one larger one - e.g. your
  42. static translation program) can solve all problems. Therefore, any fixed
  43. algorithm will break in some circumstances. Augmenting the algorithm TO ANY
  44. EXTENT CANNOT allow it to solve ALL problems. No way out.
  45.  
  46. In this case "algorithm" may be taken to mean "something which may be computed
  47. using a generalised Turing machine". Since current computers are merely
  48. sophisticated implementations of Turing machines (i.e. there exists - in the
  49. Platonic sense - a Turing machine which can completely emulate their logical
  50. behaviour), the analogy is directly applicable, because it provides a simple
  51. example of a generalised problem and makes statements about its solubility.
  52.  
  53. By the way, what happens if your static translator tries to translate a
  54. program containing bugs? Presumably your algorithm is sophisticated enough to
  55. recognise bugs when it sees them? God help us if you throw AMosaic at it...
  56.  
  57. -- Mat.
  58.